package com.leetcode.algorithm.topic;

import java.util.Arrays;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 运用递归解决树的问题
 *  “自顶向下” 的解决方案
 *      “自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 
 *      思考一下两个问题：
 *          你能确定一些参数，从该节点自身解决出发寻找答案吗？
 *          你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
 *  “自底向上” 的解决方案
 *      “自底向上” 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。
 *      思考这个问题：
 *          对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 
 * @author: jie.deng
 * @time: 2019年4月6日 上午10:03:37
 */
public class RecursiveSolution {
    /**
     * 104. 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最大深度 3 。
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // “自底向上” 的解决方案
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    
    /**
     * 101. 对称二叉树
     * 给定一个二叉树，检查它是否是镜像对称的。
     * 
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     * 
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     * 
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     * 说明:
     * 
     * 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left != null && right != null) {
            return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
        }
        return left == right;
    }
    
    /**
     * 112. 路径总和
     * 
	 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
	 * 
	 * 说明: 叶子节点是指没有子节点的节点。
	 * 
	 * 示例: 
	 * 给定如下二叉树，以及目标和 sum = 22，
	 * 
	 *               5
	 *              / \
	 *             4   8
	 *            /   / \
	 *           11  13  4
	 *          /  \      \
	 *         7    2      1
	 * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            // 叶子节点
            return root.val == sum;
        }
        sum -= root.val;
        if (root.left != null && root.right != null) {
            // 同时有左右孩子
            return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
        }
        // 只有一个孩子节点的情况
        TreeNode child = root.left == null ? root.right : root.left;
        return hasPathSum(child, sum);
    }
    
    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 
     * 根据一棵树的中序遍历与后序遍历构造二叉树。
     * 
     * 注意:
     * 你可以假设树中没有重复的元素。
     * 
     * 例如，给出
     * 
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * 返回如下的二叉树：
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        if (len == 0 || postorder.length != len) {
            return null;
        }
        if (len == 1) {
            return new TreeNode(inorder[0]);
        }
        // 找根结点:后序遍历的最后一个元素
        int val = postorder[postorder.length - 1]; // 后续遍历，最后一个元素为根结点
        TreeNode root = new TreeNode(val);
        // 左子树
        int idx = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == val) {
                idx = i; // 找中序遍历 根结点的索引，该索引左边为左子树、右边为右子树
                break;
            }
        }
        if (idx > 0) {
            root.left = buildTree(Arrays.copyOfRange(inorder, 0, idx), Arrays.copyOfRange(postorder, 0, idx));
        }
        // 右子树
        if (idx < len - 1) {
            root.right = buildTree(Arrays.copyOfRange(inorder, idx + 1, len), Arrays.copyOfRange(postorder, idx, len - 1));
        }
        return root;
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 
     * 根据一棵树的前序遍历与中序遍历构造二叉树。
     * 
     * 注意:
     * 你可以假设树中没有重复的元素。
     * 
     * 例如，给出
     * 
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * 返回如下的二叉树：
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTreeII(int[] preorder, int[] inorder) {
        int len = inorder.length;
        if (len == 0) {
            return null;
        }
        if (len == 1) {
            return new TreeNode(inorder[0]);
        }
        // 找根结点:前序遍历的第一个元素
        int val = preorder[0];
        TreeNode root = new TreeNode(val);
        // 左子树
        int idx = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == val) {
                idx = i; // 找中序遍历 根结点的索引，该索引左边为左子树、右边为右子树
                break;
            }
        }
        if (idx > 0) {
            root.left = buildTreeII(Arrays.copyOfRange(preorder, 1, idx + 1), Arrays.copyOfRange(inorder, 0, idx));
        }
        // 右子树
        if (idx + 1 < len) {
            root.right = buildTreeII(Arrays.copyOfRange(preorder, idx + 1, len), Arrays.copyOfRange(inorder, idx + 1, len));
        }
        return root;
    }
    
    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 
     * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     * 
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * 
     * 示例：
     * 
     * 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
     * 
     * 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
     * 
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
     * 
     * 提示：
     * 
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if (root == null || root.left == null || root.right == null) {
            return root;
        }
        root.left.next = root.right;
        root.right.next = root.next == null ? null : root.next.left;
        connect(root.left);
        connect(root.right);
        return root;
    }
   
    /**
     * 117. 填充每个节点的下一个右侧节点指针 II
     * 
     * 给定一个二叉树
     * 
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * 
     * 示例：
     * 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
     * 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}
     * 
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
     * 
     * 提示：
     * 
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     * @param root
     * @return
     */
    public Node connectII(Node root) {
        if (root == null) {
            return root;
        }
        Node nextSibling = getNextSibing(root);
        if (root.right != null) {
            root.right.next = nextSibling;
            connectII(root.right);
        }
        if (root.left != null) {
            root.left.next = root.right == null ? nextSibling : root.right;
            connectII(root.left);
        }
        return root;
    }

    private Node getNextSibing(Node root) {
        Node cur = root.next;
        Node child = null;
        while (cur != null && (child = cur.left == null ? cur.right : cur.left) == null) {
            cur = cur.next;
        }
        return child;
    }
    
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };   
}
